package xp.ass.imitate.algorithm.bitmap;

import java.util.Arrays;

/**
 * @author chent3
 * @date 2024/10/15
 * <p>
 * to effective compress the bitmap , we can use the roaringbitmap,
 * <p>
 * for understand RoaringBitmap, here's a simple implementation
 *
 *
 * in this code block ，we use bitMap as a container .
 *
 * in other third lib like roaringbitmap, it's more complex.
 * the roaringbitmap has two implementation of container:
 * - char array
 * - bitMap
 *
 * wo can compute the cost of them when the size achieve a threshold ,we can pick a better one
 * one bucket element can mapping a 16 bit number => 1 << 16 = 65536
 * one char => 2byte
 * use char array ==> 2 * 65536 / 1024 = 128KB
 * use bitMap ==> 65536 / 64 * 8 / 1024 = 32KB
 */
public class CompressBitMap {


    private final static int bitNum = 16;

    private final static int INIT_SIZE = 4;

    private char[] bucket;

    private BitMap[] bitMapContainer;

    private int size;

    public CompressBitMap() {
        this.bucket = new char[INIT_SIZE];
        bitMapContainer = initContainer(INIT_SIZE);
    }


    public void add(int num) {
        char hb = getHigh(num);
        char lb = getLow(num);

        int containerIndex = searchIndex(hb);
        if (containerIndex >= 0) {
            setContainerAtIndex(containerIndex, lb);
        } else {
            insertNewContainer(-containerIndex - 1, hb, lb);
        }
    }

    public boolean contain(int num) {
        char hb = getHigh(num);
        char lb = getLow(num);

        int containerIndex = searchIndex(hb);
        return containerIndex >= 0 && bitMapContainer[containerIndex].get(lb);
    }

    private void insertNewContainer(int containerIndex, char hb, char lb) {
        ensureCapacity(size + 1);
        if (bucket[containerIndex] != '0') {
            System.arraycopy(bucket, containerIndex, bucket, containerIndex + 1, size - containerIndex);
            bucket[containerIndex] = hb;
            System.arraycopy(bitMapContainer, containerIndex, bitMapContainer, containerIndex + 1, size - containerIndex);
        } else {
            bucket[containerIndex] = hb;
        }
        setContainerAtIndex(containerIndex, lb);
        size++;
    }

    private void ensureCapacity(int minSize) {
        if (minSize - bucket.length > 0) {
            grow(minSize);
        }
    }

    private void grow(int minSize) {
        int oldCapacity = bucket.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minSize < 0) {
            newCapacity = minSize;
        }
        bucket = Arrays.copyOf(bucket, newCapacity);
        BitMap[] newBitMapContainer = initContainer(newCapacity);
        System.arraycopy(bitMapContainer, 0, newBitMapContainer, 0, bitMapContainer.length);
        bitMapContainer = newBitMapContainer;
    }


    private BitMap[] initContainer(int size) {
        BitMap[] newContainer = new BitMap[size];
        for (int i = 0; i < size; i++) {
            newContainer[i] = new BitMap(1 << bitNum);
        }
        return newContainer;
    }


    private void setContainerAtIndex(int containerIndex, char lb) {
        bitMapContainer[containerIndex].put(lb);
    }


    private char getHigh(int num) {
        return (char) (num >>> bitNum);
    }

    // F express 4 bit 1111 => 2^0 + 2^1 + 2^2 + 2^3 = 15
    private char getLow(int num) {
        return (char) (num & 0X0000FFFF);
    }


    private int searchIndex(char searchKey) {
        int lowIndex = 0;
        int highIndex = size > 0 ? size - 1 : -1;
        while (lowIndex <= highIndex) {
            int midIndex = (lowIndex + highIndex) >>> 1;
            char midVal = bucket[midIndex];

            if (midVal == searchKey) {
                return midIndex;
            }

            if (searchKey < midVal) {
                highIndex = midIndex - 1;
            } else {
                lowIndex = midIndex + 1;
            }
        }
        return -(lowIndex + 1);
    }
}
